public class Solution5 {
    public String longestPalindrome(String s) {
        boolean[][] f=new boolean[s.length()][s.length()];
        int ans=1;
        String ss=s.substring(0,1);
        for (int i=s.length()-1;i>=0;i--){
            f[i][i]=true;
            if (i!=s.length()-1){
                f[i][i+1]=s.charAt(i)==s.charAt(i+1);
                if (f[i][i+1] && ans<2){
                        ans = 2;
                        ss=s.substring(i,i+2);
                }
            }
            for (int j=i+2;j<s.length();j++){
                f[i][j]=s.charAt(i)==s.charAt(j)&&f[i+1][j-1];
                if (f[i][j] && ans<j-i+1) {
                    ans=j-i+1;
                    ss=s.substring(i,j+1);
                }
            }
        }
        return ss;
    }

    public static void main(String[] args) {
        System.out.println(new Solution5().longestPalindrome("babad"));
    }
}
